package kyssion.leetcode.num151_200;

import java.util.Arrays;

public class code169_求众数 {
    public static void main(String[] args) {

    }

    int midle = 0;

    public int majorityElement(int[] nums) {
        if (nums.length == 0) {
            return nums[0];
        }
        Arrays.sort(nums);
        return nums[nums.length/2+1];
    }

    /**
     * 巧妙写法 -- 动态规划的思想 --
     * 假如到了第n位 发现之前没有众数(叠加值等于1) 那么就可以保证n+1-最后的众数肯定是0-最后的众数,重新初始化计算即可
     * 如果到了第n位,n-1发现有众数 , 如果之前的众数等于n的数 那么叠加值+1否则减一
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        int count=0;//计算当前的数字出现的次数
        int mj=0;// 当前判断的元素
        for (int i = 0; i < nums.length; i++) {
            if(count==0){//当次数为0时，则换下一判断元素
                mj=nums[i];
                count=1;
            } else if (nums[i]==mj) {
                count++;//当前元素等于判断元素，次数加一
            } else {
                count--;//不等于则次数减一
            }
        }
        return mj;
    }
}
